#include <stdio.h>
#include <stdlib.h>

#define MEM_SIZE 8096
#define BLOCK_SIZE 64

char mem[MEM_SIZE];

typedef struct Block {
    size_t start;
    size_t size;
    int is_free;
    struct Block *next;
} Block;

Block *head = NULL;

void *umalloc(size_t size) {
    Block *curr = head;
    Block *prev = NULL;

    while (curr) {
        if (curr->is_free && curr->size >= size) {
            // 分配该块
            curr->is_free = 0;
            size_t rest_size = curr->size - size;
            if (rest_size != 0) {
                // 切割该块
                Block *rest = (Block *)malloc(sizeof(Block));
                rest->start = curr->start + size;
                rest->size = rest_size;
                rest->is_free = 1;
                rest->next = curr->next;
                curr->next = rest;
                curr->size = size;
            }
            return (void *)(mem + curr->start);
        }
        prev = curr;
        curr = curr->next;
    }

    return NULL;
}

void ufree(void *ptr) {
    size_t addr = (char *)ptr - mem;

    Block *curr = head;
    Block *prev = NULL;

    while (curr) {
        if (curr->start <= addr && addr < curr->start + curr->size) {
            curr->is_free = 1;
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

void umerge() {
    Block *curr = head;
    Block *next = curr->next;

    while (next) {
        if (curr->is_free && next->is_free) {
            // 合并相邻的空闲块
            curr->size += next->size;
            curr->next = next->next;
            next = curr->next;
        } else {
            curr = next;
            next = next->next;
        }
    }
}

void print() {
    Block *curr = head;
    int index = 0;

    while (curr) {
        printf("块 %d: [开始地址：%p, 大小: %ld, 空闲: %s]\n", index++, mem + curr->start, curr->size, curr->is_free ? "是" : "否");
        curr = curr->next;
    }
}

void close() {
    Block *prev = head;
    Block *curr = head->next;

    while (prev) {
        free(prev);
        prev = curr;
        if (curr) curr = curr->next;
    }
}

int main() {
    head = (Block *)malloc(sizeof(Block));
    head->start = 0;
    head->size = MEM_SIZE;
    head->is_free = 1;
    head->next = NULL;

    printf("初始内存分块情况: \n");
    print();
    printf("\n");

    // 分配内存
    int *ptr1 = umalloc(sizeof(int));
    if (ptr1 == NULL) return 1;
    *ptr1 = 19;
    unsigned long long *ptr2 = umalloc(sizeof(unsigned long long));
    if (ptr2 == NULL) return 1;
    *ptr2 = 18446744073709551615LLU;
    short *ptr3 = umalloc(sizeof(short));
    if (ptr3 == NULL) return 1;
    *ptr3 = -32768;

    printf("分配了内存地址: %p, 大小: %lu, 值: %d\n", ptr1, sizeof(*ptr1), *ptr1);
    printf("分配了内存地址: %p, 大小: %lu, 值: %llu\n", ptr2, sizeof(*ptr2), *ptr2);
    printf("分配了内存地址: %p, 大小: %lu, 值: %d\n", ptr3, sizeof(*ptr3), *ptr3);
    printf("\n");

    printf("分配后的内存分块情况: \n");
    print();
    printf("\n");

    // 释放内存
    ufree(ptr1);
    ufree(ptr3);

    printf("释放了内存地址: %p\n", ptr1);
    printf("释放了内存地址: %p\n", ptr3);
    printf("\n");

    printf("释放后的内存分块情况: \n");
    print();
    printf("\n");

    // 碎片整理
    umerge();

    printf("整理后的内存分块情况: \n");
    print();
    printf("\n");

    close();
    return 0;
}